package 面试刷题.小米;

import org.junit.experimental.max.MaxHistory;

import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;
import java.util.concurrent.locks.ReentrantLock;

public class ch07_递推 {
    static int maxn = 30000 + 10;
    static long maxi = (int) (1e9 + 10);
    static long[] arr = new long[maxn];
    // 定义动态规划 dp 数组，dp[i][0] 表示第 i 个元素不取反的最大和，dp[i][1] 表示第 i 个元素取反的最大和
    static Long[][] dp = new Long[maxn][2];
    static int n;

    public static void main(String[] args) {
        verify(1000);
//        main();
    }

    public static void main() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextLong();
        }
        System.out.println(dfs(0, 0));
    }

    public static void verify(int cnt) {
        Random r = new Random();
        for (int c = 0; c < cnt; c++) {
            int n = r.nextInt(maxn)/10 + 1;
            long[] arr = new long[n];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = r.nextInt((int) maxi);
                if (r.nextBoolean()) {
                    arr[i] = -arr[i];
                }
            }
            long ans = ans(n, arr);
            long my = my(n, arr);
            if (ans != my) {
                System.out.println("结果不一致 ans:" + ans + ";  my : " + my);
                System.out.println(n + ":" + Arrays.toString(arr).replaceAll(",", ""));
            }
        }

    }

    public static long my(int n, long[] arr) {
        dp = new Long[n + 10][2];
        ch07_递推.n = n;
        ch07_递推.arr = arr;
        return dfs(0, 0);
    }

    public static long ans(int n, long[] arr) {
        int cnt = 0, min = Integer.MAX_VALUE;
        long sum = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < 0) cnt++;
            long abs = Math.abs(arr[i]);
            min = (int) Math.min(min, abs);
            sum += abs;
        }
        if (cnt % 2 == 0) {
            return sum;
        } else {
            return sum - min * 2L;
        }
    }

    // 定义 dfs 函数，cur 表示当前遍历到的数组下标，not 表示当前元素是否取反（0 表示不取反，1 表示取反）
    public static long dfs(int cur, int not) {
        // 如果 dp[cur][not] 已经计算过，直接返回结果
        if (dp[cur][not] != null) {
            return dp[cur][not];
        }
        // 根据 not 值决定当前元素是否取反
        long currValue = not == 0 ? arr[cur] : -arr[cur];
        // 如果当前是最后一个元素，则返回其值（处理边界情况）
        if (cur == n - 1) return currValue;
        // 递归计算当前元素不取反的情况下，后续元素的最大和
        long noNot = dfs(cur + 1, 0) + currValue;
        // 递归计算当前元素取反的情况下，后续元素的最大和
        long isNot = dfs(cur + 1, 1) - currValue;
        // 取不取反两种情况中的较大值作为 dp[cur][not] 的值
        dp[cur][not] = Math.max(noNot, isNot);
        return dp[cur][not];
    }
}
